package Top200;

/**
 * @author zhangmin
 * @create 2022-02-21 14:36
 * 下一个排序：是将一个靠近后面的大数与一个靠近前面的小数的交换，然后使得大数位置之后的所有元素升序---找到一个尽可能小的大数换到一个尽可能大的小数的位置
 * 将从后向前第一个变小的元素作为小数，再从后向前找到i<k的k作为大数，交换i和k后将j之后的元素升序
 */
public class nextPermutation31 {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        if (n<=1) return;
        int i=n-2,j=n-1,k=n-1;
        //找到从后向前的第一个变小的数，i作为小数
        for (; i >=0 ; i--,j--) {
            if (nums[i]<nums[j]) break;
        }
        if (i>=0){
            //说明不是最后一个排序
            //找到从j之后刚好比nums[i]大的最小的数
            while (nums[i]>=nums[k]&&k>=j){
                k--;
            }
            swap(nums,i,k);
        }
        reverse(nums,j);
    }
    void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
    void reverse(int[] nums,int start){
        int left=start,right=nums.length-1;
        while (left<right){
            swap(nums,left,right);
            left++;right--;
        }
    }
}
